package com.xiaoyg.algorithm;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class NextGreaterElement {



    public int [] nextGreaterElement(int [] num1,int [] num2){
        int [] greater = nextGreaterElement(num2);
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < num2.length; i++) {
            map.put(num2[i], greater[i]);
        }

        int [] res = new int [num1.length];
        for (int i = 0 ;i <num1.length;i++ ){
            res[i] = map.get(num1[i]);
        }
        return res;
    }

    public int [] nextGreaterElement(int [] nums){
        int n = nums.length;
        int [] greater = new int [n];
        Stack<Integer> stack = new Stack<>();
        for (int i = n - 1; i > 0; i++) {
            while (!stack.isEmpty() && stack.peek() <= nums[i]){
                stack.pop();
            }
            greater[i] = stack.isEmpty()? -1 : stack.peek();
            stack.push(nums[i]);
        }
        return greater;
    }


}
